Restricted isometry property

In linear algebra, the restricted isometry property characterizes matrices which are nearly orthonormal, at least when operating on sparse vectors. The concept was introduced by Emmanuel Candès and Terence Tao[1] and is used to prove many theorems in the field of compressed sensing.[2] There are no known large matrices with bounded restricted isometry constants, but many random matrices have been shown to remain bounded. The current smallest upper bounds for any large rectangular matrices are for those of Gaussian matrices[3]. Web forms to evaluate bounds for the Gaussian ensemble are available at the Edinburgh Compressed Sensing RIC page[4].

Definition

Let A be an m × p matrix and let s < p be an integer. Suppose that there exists a constant \delta_s such that, for every m × s submatrix As of A and for every vector y,

(1-\delta_s)\|y\|_{\ell_2}^2 \le \|A_s y\|_{\ell_2}^2 \le (1%2B\delta_s)\|y\|_{\ell_2}^2. \,

Then, the matrix A is said to satisfy the s-restricted isometry property with restricted isometry constant \delta_s.

See also

References

  1. ^ E. J. Candes and T. Tao, "Decoding by Linear Programming," IEEE Trans. Inf. Th., 51(12): 4203–4215 (2005).
  2. ^ E. J. Candes, J. K. Romberg, and T. Tao, "Stable Signal Recovery from Incomplete and Inaccurate Measurements," Communications on Pure and Applied Mathematics, Vol. LIX, 1207–1223 (2006).
  3. ^ B. Bah and J. Tanner "Improved Bounds on Restricted Isometry Constants for Gaussian Matrices"
  4. ^ http://ecos.maths.ed.ac.uk/ric_bounds.shtml